package com.dmall.sort.algorithm;

/**
 * 计数排序
 * @author xiao1.wang
 * @date 2021/10/10 17:27
 */
@SuppressWarnings("all")
public class CountingSort implements Sort {

    @Override
    public void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int max = arr[0], min = max;
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
            if (min > arr[i]) {
                min = arr[i];
            }
        }
        countingSort(arr, min, max);
    }

    private void countingSort(int[] arr, int min, int max) {
        int range = max - min + 1;
        int[] count = new int[range];
        for (int num : arr) {
            count[num - min] ++;
        }
        int[] index = new int[range + 1];
        for (int i = 0; i < range; i++) {
            index[i + 1] = index[i] + count[i];
        }
        for (int i = 0; i + 1 < index.length; i++) {
            for (int j = index[i]; j < index[i + 1]; j++) {
                arr[j] = i + min;
            }
        }
    }

    @Override
    public String getName() {
        return "计数排序";
    }

    public static void main(String[] args) {
        int[] arr = {6, 9, 4, 7, 2, 8, 3, 1, 10, 5};
        Sort.printArr(arr);
        Sort sort = new CountingSort();
        sort.sort(arr);
        Sort.printArr(arr);
    }
}
